COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	equiva[w88,jmc]		Equivalence classes as first class objects
C00005 ENDMK
C⊗;
equiva[w88,jmc]		Equivalence classes as first class objects

	In mathematics, two of the main operations for constructing
new sorts of entities from old are cartesian product and forming
the set of equivalence classes under an equivalence relation.  For
example, the rational numbers are usually defined as the equivalence
classes of an equivalence relation on pairs of integers.  Many programming
languages allow cartesian product as a way of forming new
data ``types'', but equivalence classes aren't available in
any that I know of.

	In my opinion, this isn't just because no-one has thought of it.
Indeed the possibility is also mentioned in (McCarthy 1963) which first, I
think, proposed cartesian product.  There is a real difficulty.  Namely,
it isn't hard to implement a standard way of representing elements of
cartesian products as data structures that provides reasonable efficiency
--- at least when cartesian products are not used recursively.  Therefore,
the implementer of the language can provide for them in a straightforward
manner.  Even so, cartesian products are often not treated as first class
objects in that a notation for constants is often not provided.

	Providing for equivalence classes is much harder.  There doesn't
seem to be a standard way of doing it that provides efficiency.  The
obvious way of doing it is to pick a member of each equivalence
class as the representative of the class.  However, this requires